Exponentiation by Squaring Algorithm
The Exponentiation by Squaring Algorithm is an efficient method for computing large powers of a base number with a given exponent, especially when dealing with modular arithmetic. This algorithm is based on the simple observation that when the exponent is even, the base can be squared while the exponent is halved, and when the exponent is odd, the base can be multiplied by itself raised to the power of one less than the exponent. By breaking down the exponentiation process into smaller subproblems, the algorithm significantly reduces the number of multiplication operations required, making it a faster and more efficient approach compared to the naive method of multiplying the base by itself repeatedly for the exponent number of times.
To better understand the algorithm, let's illustrate it with an example. Suppose we want to compute 3^13. The algorithm starts by checking if the exponent is even or odd. Since 13 is odd, we multiply the base (3) by itself raised to the power of (13-1), which is 3^12. Now, we need to compute 3^12, which is an even exponent, so we can square the base and halve the exponent, resulting in 3^6. Continuing with this pattern, we compute 3^3 by multiplying the base (3) by itself raised to the power of (6-1), which is 3^5. Eventually, we reach the point where the exponent is 1, and the base raised to the power of 1 is just the base itself. By combining the results of these smaller subproblems, we obtain the final result of 3^13. This method requires far fewer multiplications than the naive method and can be easily implemented in a recursive or iterative manner, making it an efficient algorithm for large-scale exponentiation computations.
/*
Petar 'PetarV' Velickovic
Algorithm: Exponentiation by Squaring
*/
#include <stdio.h>
#include <math.h>
#include <string.h>
#include <iostream>
#include <vector>
#include <list>
#include <string>
#include <algorithm>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <complex>
using namespace std;
typedef long long lld;
//Algoritam za stepenovanje kvadriranjem po datom modulu i za racunanje modularnog inverza (pod uslovom da je modul prost)
//Slozenost O(log N)
inline lld mod_pow(lld num, lld pow, lld mod)
{
lld ret = 1;
while (pow)
{
if (pow&1)
{
ret = (ret*num)%mod;
}
pow>>=1;
num = (num*num)%mod;
}
return ret;
}
inline lld mod_inv(lld num, lld mod)
{
return mod_pow(num, mod-2, mod);
}
int main()
{
printf("%lld\n",mod_pow(5,2,10));
printf("%lld\n",mod_inv(1423,13));
return 0;
}
